//SD_class_Alg.cpp---------------数独类中去重算法的定义
//
//	bool SD_C::FindSole(int, int);			//唯一填数法，用已知空去除不可能候选数
//	bool SD_C::FindSoleAble(int, int);		//唯余填数法，用未知空保留唯一可能候选数
//  void SD_C::AllFind();                   //综合运用唯一法和唯余法刷新s和q
//	void SD_C::SmallXY();					//找候选数最少的位置
//
//v.1.0------------------------------------------------------------------

#include<iostream>

#include"SD_class.h"

using namespace std;

//1.唯一法
//   @return	true   有改变
//				false  无改变
bool SD_C::FindSole(int i, int j)
{
    short sum, sum_row, sum_col, sum_squ;						//行、列、宫
    short old = 0;
    //cout<<"s["<<i<<"]["<<j<<"]:";
    //Print_bit(s[i][j]);
    //cout<<endl;

	if (CountOneBit(s[i][j]) > 1)								//排除已填的空
	{
		old = s[i][j];

        sum_squ = 0;
		for (int i0 = i / 3 * 3; i0 < i / 3 * 3 + 3; i0++)		// 遍历小九宫，找出已有数
			for (int j0 = j / 3 * 3; j0 < j / 3 * 3 + 3; j0++)
				if (CountOneBit(s[i0][j0]) == 1)
                    sum_squ += s[i0][j0];                   	//宫中不可能数集合

        sum_row = 0;
		for (int j0 = 0; j0 < 9; j0++)							// 遍历横排，找出已有数
			if (CountOneBit(s[i][j0]) == 1)
                sum_row += s[i][j0];                        	//行不可能数集合

        sum_col = 0;
        for (int i0 = 0; i0 < 9; i0++)							// 遍历纵排，找出已有数
			if (CountOneBit(s[i0][j]) == 1)
                sum_col += s[i0][j];                        	//列不可能数集合

        sum = sum_squ | sum_row | sum_col;                  	//行、列、宫不可能数并集
		
        //cout<<"    sum:";
        //Print_bit(sum);
        //cout<<endl;

        s[i][j] &= ~sum;                                		//从n中排除不可能数,原理：&1不变，&0变成0
        //cout<<"    old:";
        //Print_bit(old);
        //cout<<endl;
        //cout<<"    new:";
        //Print_bit(s[i][j]);
        //cout<<endl;

        if (s[i][j] == 0)                               		//候选数为0，出错，进行重置，退出
		{
			s[i][j] = old;
            //cout<<"候选数为0，false"<<endl;
			return false;
		}
        else if (s[i][j] != old)                        		//缩小了候选数范围，退出
        {
            //cout<<"缩小了候选数，ture"<<endl;
            return true;
        }
		else													//候选数范围没有缩小，不进行任何操作直接退出
        {
            //cout<<"候选数无变化，false"<<endl;
            return false;
        }
	}
    //cout<<"已填空，false"<<endl;
	return false;												//该空有已知数，退出
}

//2.唯余法
//   原理：&1值不变，&0变成0
//   @return	true   有改变
//				false  无改变
bool SD_C::FindSoleAble(int i, int j)
{
    short old_s = s[i][j];          							//用于暂存当前空
    //cout<<"s["<<i<<"]["<<j<<"]:";
    //Print_bit(s[i][j]);
    //cout<<endl;

    if (CountOneBit(s[i][j]) > 1)                              	//排除已填的空
	{
        short new_s = s[i][j];                                  //暂存当前空
        //cout<<"    old:";
        //Print_bit(old_s);
        //cout<<endl;

		//squ
		for (int i0 = i / 3 * 3; i0 < i / 3 * 3 + 3; i0++)
			for (int j0 = j / 3 * 3; j0 < j / 3 * 3 + 3; j0++)
				if (i0 != i || j0 != j)							//排除当前空
                    s[i][j] &= ~s[i0][j0];                      //去除其余空的可能数值
        //cout<<"   -squ:";
        //Print_bit(s[i][j]);
        //cout<<endl;
        if (s[i][j] == 0)
            s[i][j] = new_s;
        else
            new_s = s[i][j];

		//row
		for (int i0 = 0; i0 < 9; i0++)
			if (i0 != i)										//排除当前空
                s[i][j] &= ~s[i0][j];                       	//去除其余空的可能数值
        //cout<<"   -row:";
        //Print_bit(s[i][j]);
        //cout<<endl;
        if (s[i][j] == 0)
            s[i][j] = new_s;
        else
            new_s = s[i][j];

		//col
		for (int i0 = 0; i0 < 9; i0++)
			if (i0 != i)										//排除当前空
                s[i][j] &= ~s[i0][j];                       	//去除其余空的可能数值
        //cout<<"   -col:";
        //Print_bit(s[i][j]);
        //cout<<endl;
        if (s[i][j] == 0)
            s[i][j] = new_s;
        else
            new_s = s[i][j];


        if (new_s != old_s)                             		//缩小了候选数范围，退出
        {
            //cout<<"缩小了候选数，true"<<endl;
            return true;
        }
        else													//候选数范围没有缩小，不进行任何操作直接退出
        {
            //cout<<"候选数无变化，false"<<endl;
            return false;
        }
	}
    //cout<<"已填空，false"<<endl;
	return false;
}

//3.综合运用唯一法和唯余法刷新s和q
void SD_C::AllFind()
{
    bool change;
    do
    {
        change = false;
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
            {
                change += FindSole(i, j);
                Update_q();
                change += FindSoleAble(i, j);
                Update_q();
                //TO DO加入其他算法
            }
    } while (change);
}

//3.找候选数最少的位置坐标
void SD_C::SmallXY()
{
	int smallCount = 10;										//存储遍历过的位置中的最少候选数，初始设为10，因为最大可能为9

	for (int i = 0; i < 9; i++)									//遍历整个数组
	{
		for (int j = 0; j < 9; j++)
		{
			int bitcount = CountOneBit(s[i][j]);				//存储当前位置的候选数个数

			if (bitcount == 2)									//2个候选数是最少的可能了，直接返回该位置，程序结束
            {
                x = i;
                y = j;
			}
			else if (bitcount > 2)								//候选数多于2个
			{
                if (smallCount > bitcount)						//候选数少于前一个位置的候选数个数
				{
					smallCount = bitcount;
                    x = i;									//将当前位置缓存入XY
                    y = j;
				}
			}
		}
	}
}
